//
// Created by wenyaxi on 24-10-30.
//
#include <common.h>

class Solution {
public:
    int x_direct[4] = {0, 1, 0, -1};
    int y_direct[4] = {1, 0, -1, 0};
    int direct = 0;
    vector<int> path;

    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        dfs(0, 0, visited, matrix);
        return path;
    }

    void dfs(int x, int y, vector<vector<bool> > &visited, vector<vector<int> > &matrix) {
        if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() || visited[x][y]) {
            direct = (direct + 1) % 4;
            return;
        }
        path.push_back(matrix[x][y]);
        visited[x][y] = true;
        for (int k = 0; k < 4; k++) {
            dfs(x + x_direct[direct], y + y_direct[direct], visited, matrix);
        }
    }
};

int main(int argc, char *argv[]) {
    Solution s;
    vector<vector<int> > matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16},
        {17, 18, 19, 20},
        {21, 22, 23, 24},
    };
    auto spiral_order = s.spiralOrder(matrix);
    cout << printer::int_array_to_string(spiral_order) << endl;
    return 0;
}
